package bintree.heap.LeetCode;

//347. 前 K 个高频元素 --- 取大用小
//请你返回其中出现频率前 k 高的元素。

/**
 * 思路在优先级队列那边博客力扣题里面有讲，自定义一个类，保存这个类的对象。
 */

import java.util.*;

/**
 *  这个类的对象就是数组中的元素以及出现的频次
 *   在优先级队列中，保存的就是这个类的对象
 */
class Freq implements Comparable<Freq> {
    //数组中出现的元素
    int key;
    //数组中出现的频次
    int value;

    @Override //覆写比较方法
    public int compareTo(Freq o) {
        return this.value - o.value;
    }
    //构造方法
    public Freq(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class Num347_topKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        //1. 先扫描原数组，讲出现的元素以及其频次保存到Map集合中。
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums){
            if (map.containsKey(i)){
                //说明此时元素 i 已经出现过，现在就只需要把频次 + 1即可
                int times = map.get(i);//get:获取当前 i 出现的频次
                map.put(i, times + 1);//put: i这个元素的频次变为原来的值+1
            }else{
                //说明此时的 i 是第一次出现，就将该元素保存到map中
                map.put(i,1);//i这个元素，频次为 1
            }

        } //扫描完成后： //举例 [1,1,1,2,2,3] => {{1 : 3},{2 : 2}, {3 : 1} }

        // 2.扫描 Map集合，将出现频次最高的前k个元素添加到优先级队列中
        //所以先创建一个优先级队列
        Queue<Freq> queue = new PriorityQueue<>();
        //遍历map集合 //注释：Map.Entry 相当于里面的元素类型 如：int【】 里面是 int
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){

            if(queue.size() < k){
                //说明需要存入元素到队列里面
                queue.offer(new Freq( entry.getKey(), entry.getValue()) );
            }else{                  //注释：entry表示元素跟以前写的int i ：arr 一样
                //不需要盲目存入元素了，判断堆顶元素和当前元素的频次
                //最小堆，如果新的元素比树顶值还小，肯定不是我们想要的值
                // 比树顶值大的元素，入队。打擂台思想，最后k个就是最大的
                Freq freq = queue.peek();//查看当前堆的最小值
                if(entry.getValue() > freq.value){
                    queue.poll();//出队一个元素
                    queue.offer(new Freq(entry.getKey(), entry.getValue()));
                }

            }
        }//for

        // 3.此时队列中就保存了出现频次最大的前k个数对 - k个Freq对象
        // 遍历队列，将Freq对象中的key取出放入结果集中即可
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().key;
        }
        return ret;
    }
}
